package likou.jindian;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/12/08 07:29
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class _04_04 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);
//        root.left.left = new TreeNode(3);
//        root.left.right = new TreeNode(3);
//        root.left.left.left = new TreeNode(4);
//        root.left.left.right = new TreeNode(4);
        System.out.println(isBalanced(root));

    }

    static boolean daan = true;
    static boolean p = true;

    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return daan;
        }
        search(root);
        return daan;
    }

    public static int search(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (p) {
            if (root.left == null && root.right == null) {
                return 1;
            }
            int leftNum = 1, rightNum = 1;
            if (root.left != null) {
                leftNum = 1 + search(root.left);
            }
            if (root.right != null) {
                rightNum = 1 + search(root.right);
            }
            if (Math.abs(rightNum - leftNum) > 1) {
                daan = false;
                p = false;
            }
            return Math.max(leftNum, rightNum);
        }
        return 0;
    }

    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        return isBalanced2(root.left) && isBalanced2(root.right);
    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
    public boolean isBalanced3(TreeNode root) {
        if (root==null){
            return true;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        if (Math.abs(left-right)>1){
            return false;
        }
        return isBalanced3(root.left)&&isBalanced3(root.right);
    }
    
}
